﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Collections;

namespace Problem0010
{
	// Calculate the sum of all the primes below two million.
	class Project0010
	{
		static void Main(string[] args)
		{
			var numbers = SieveEratosthenes(2000000);
			long total = 0;
			foreach (var num in numbers)
				total += num;
			Console.Write(total);
			Console.Read();
		}

		// Sieve of Eratosthenes
		public static int[] SieveEratosthenes(int upperLimit)
		{
			int sieveBound = (int)(upperLimit - 1) / 2;
			int upperSqrt = ((int)Math.Sqrt(upperLimit) - 1) / 2;

			BitArray PrimeBits = new BitArray(sieveBound + 1, true);

			for (int i = 1; i <= upperSqrt; i++)
			{
				if (PrimeBits.Get(i))
				{
					for (int j = i * 2 * (i + 1); j <= sieveBound; j += 2 * i + 1)
					{
						PrimeBits.Set(j, false);
					}
				}
			}

			List<int> numbers = new List<int>((int)(upperLimit / (Math.Log(upperLimit) - 1.08366)));
			numbers.Add(2);

			for (int i = 1; i <= sieveBound; i++)
			{
				if (PrimeBits.Get(i))
				{
					numbers.Add(2 * i + 1);
				}
			}

			return numbers.ToArray();
		}
	}
}
